﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace psieve.sieve
{
    // loosely based on http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf
    public class Eratosthenes2 : ISieve
    {
        private readonly int[] deltas = {1, 7, 11, 13, 17, 19, 23, 29};

        private readonly int[][] cycles = new int[8][];

        public Eratosthenes2()
        {
            for (int d = 0; d < 8; d++)
            {
                cycles[d] = new int[30];

                for (int r = 1; r < 30; r += 2)
                {
                    if(r % 3 == 0 || r % 5 == 0)
                        continue;

                    cycles[d][r] = CountCycles(r, deltas[d], 30); ;
                }
            }
        }

        private static int CountCycles(int rem, int delta, int b)
        {
            int s = rem;

            for (int x = 1;; x++)
            {
                s += rem;

                if (s > delta)
                    s -= b;

                if (s == delta)
                    return x + 1;
            }
        }

        private int FindFirstK2(int d, int q)
        {
            int rem = q%30;
            int c = cycles[d][rem];

            if (c == 0)
                throw new ApplicationException("c=0");

            int k = (int) ((q*(long) c - deltas[d])/30);

            //long check1 = k * 30L + deltas[d];
            //long check2 = q * (long) c;

            //if(check1 != check2)
            //    throw new ApplicationException(check1 + "!=" + check2);

            return k;
        }

        private void Filter(int B, BitArray ray, int d, int q)
        {
            int firstK = FindFirstK2(d, q);

            for (int k = firstK; k <= B; k += q)
                ray[k] = false;
        }

        private void Filter(int B, BitArray[] rays, int q)
        {
            for (int d2 = 0; d2 < 8; d2++)
                Filter(B, rays[d2], d2, q);
        }

        public IEnumerable<long> Sieve(int end)
        {
            int L = 0;
            int B = end / 30;

            BitArray[] rays = new BitArray[8];
            for(int d = 0; d < 8; d++)
                rays[d] = new BitArray(B + 1, true);

            yield return 2;
            yield return 3;
            yield return 5;

            for (int d = 1; d < 8; d++)
            {
                int p = deltas[d];
                yield return p;

                Filter(B, rays, p);
            }

            for (int k = 1; k <= B; k++)
            {
                int k30 = k*30;

                for(int d = 0; d < 8; d++)
                    if (rays[d][k])
                    {
                        int p = k30 + deltas[d];
                        
                        if(p > end)
                            yield break;
                        
                        yield return p;

                        Filter(B, rays, p);
                    }
            }
        }
    }
}
